package Algorithms;

import org.junit.Test;

import java.util.ArrayList;

/**
 * 快速排序
 * 非稳定排序
 * 平均时间复杂度O(n * logn)
 * 最坏 O(n^2) 退化为没有改进的冒泡排序
 */
public class Quicksort {
    @Test
    public void test() {
        int[] nums = {4,3,6,72,3,9,5,2,3,6,86,43};
        quickSort(nums,0,nums.length-1);
        for (int num : nums) {
            System.out.print(num+" ");
        }
    }

    public void quickSort(int[] nums, int left, int right){
        if (left<right){ //加上这个，不然有死循环，造成堆栈溢出，这也是递归结束条件 ！！！！
            int milestone = partition(nums,left,right);
            quickSort(nums, left, milestone-1);
            quickSort(nums, milestone+1, right);
        }
    }

    /**
     *
     * @param nums  数组
     * @param left  数组左界标
     * @param right 数组右界标
     */
    public int partition(int[] nums, int left, int right){
        int i = left, j = right;
        int milestone = nums[i];
        while (i<j){
            while (i<j && nums[j] > milestone){ //在右边找一个比界碑小的元素
                j--;
            }
            if (i<j){
                nums[i] = nums[j];
                i++;
            }
            while (i<j && nums[i] < milestone){ //在左边找一个比界碑大的元素 !!!!=
                i++;
            }
            if (i<j){
                nums[j]=nums[i];
                j--;
            }
        }
        nums[i]=milestone;
        return i;
    }
}
